package pl.poznan.put.cs.to.tsp.hea;

import java.util.Collections;
import java.util.HashSet;
import java.util.Iterator;
import java.util.LinkedList;
import java.util.List;
import java.util.Random;
import java.util.Set;

import pl.poznan.put.cs.to.tsp.common.IResultHolder;
import pl.poznan.put.cs.to.tsp.common.Vertexes;
import pl.poznan.put.cs.to.tsp.localsearch.Edge;

public class HEAResultCrosser implements IResultHolder {
	private IResultHolder firstResult;
	private IResultHolder secondResult;

	private LinkedList<Integer> listA;
	private LinkedList<Integer> listB;
	private int lengthA;
	private int lengthB;
	private Vertexes vertexes;

	private Set<Edge> commonEdges;
	private List<Integer> availableVertexes;
	private int[] vertexCountVector;
	private int[][] vertexNeighbours;

	private LinkedList<Integer> llA;
	private LinkedList<Integer> llB;
	private LinkedList<Integer> rest;

	private int sameInA;
	private int sameInB;

	private int vertexesToAdd;

	public HEAResultCrosser(IResultHolder firstResult,
			IResultHolder secondResult, Vertexes vertexes) {
		// System.out.println("> CROSSING STARTED <");

		this.firstResult = firstResult;
		this.secondResult = secondResult;
		this.vertexes = vertexes;

		this.init();

		// System.out.println("AvailableVertexes:");
		this.printList(this.availableVertexes);
		// System.out.println();

		// System.out.println("Available A:");
		this.printList(llA);
		// System.out.println();

		// System.out.println("Available B:");
		this.printList(llB);
		// System.out.println();

		// System.out.println("Rest:");
		this.printList(rest);
		// System.out.println();

		this.printVertexNeighbours();

		this.generateResult();
		// System.out.println("> CROSSING FINISHED! <");
	}

	private void cleanupAvailables(List<Integer> tabu) {
		for (Integer i : tabu) {
			if (this.llA.contains(i)) {
				this.llA.remove(this.llA.indexOf(i));
			}
			if (this.llB.contains(i)) {
				this.llB.remove(this.llB.indexOf(i));
			}
			if (this.rest.contains(i)) {
				this.rest.remove(this.rest.indexOf(i));
			}
		}
	}

	private int calculateLength(List<Integer> res1) {
		LinkedList<Integer> res = new LinkedList<Integer>(res1);
		int distance = 0;
		int first = res.getFirst();
		int last = res.getLast();
		int before = -1;

		for (Integer i : res) {
			if (before == -1) {
				distance += this.vertexes.getDistanceBetween(first, last);
			} else {
				distance += this.vertexes.getDistanceBetween(before, i);
			}
			before = i;
		}

		return distance;
	}

	private void generateResult() {
		this.vertexesToAdd = this.vertexes.getNumberOfNodes();

		this.listA = new LinkedList<Integer>();
		this.listB = new LinkedList<Integer>();

		if (this.sameInA == this.firstResult.getListA().size()) {
			if (this.sameInB == this.firstResult.getListB().size()) {
				this.listA = this.firstResult.getListA();
				this.listB = this.firstResult.getListB();
				this.lengthA = this.firstResult.getLengthA();
				this.lengthB = this.firstResult.getLengthB();
				this.vertexesToAdd = 0;
				// System.out.println("Both results same!");
				return;
			} else {
				this.listA = this.firstResult.getListA();
				this.lengthA = this.firstResult.getLengthA();
				// System.out.println("Copying listA:");
				this.printList(this.listA);
				this.printList(this.listB);
				this.vertexesToAdd -= this.listA.size();
				// System.out
				// .println("Result A is the same - generating only result B!");
				this.cleanupAvailables(this.listA);
				this.generateOneList(EOrigin.A);
				return;
			}
		}
		if (this.sameInB == this.firstResult.getListB().size()) {
			this.listB = this.firstResult.getListB();
			this.lengthB = this.firstResult.getLengthB();
			// System.out.println("Copying listB:");
			this.printList(this.listA);
			this.printList(this.listB);
			this.vertexesToAdd -= this.listB.size();
			// System.out
			// .println("Result B is the same - generating only result A!");
			this.cleanupAvailables(this.listB);
			this.generateOneList(EOrigin.B);
			return;
		}

		// System.out.println("Generating both results!");

		Random r = new Random();
		int startA;
		int startB;
		int v;

		if (this.llA.size() > 0) {
			startA = r.nextInt(this.llA.size());
			v = this.llA.remove(startA);
			if (this.isPartMember(v)) {
				LinkedList<Integer> part = this.processPathPart(v, this.llA);
				this.listA.addAll(part);
				this.vertexesToAdd = this.vertexesToAdd - part.size();
			} else {
				this.listA.add(v);
				this.vertexesToAdd--;
			}
		} else {
			startA = r.nextInt(this.rest.size());
			v = this.rest.remove(startA);
			if (this.isPartMember(v)) {
				LinkedList<Integer> part = this.processPathPart(v, this.rest);
				this.listA.addAll(part);
				this.vertexesToAdd = this.vertexesToAdd - part.size();
			} else {
				this.listA.add(v);
				this.vertexesToAdd--;
			}
		}

		if (this.llB.size() > 0) {
			startB = r.nextInt(this.llB.size());
			v = this.llB.remove(startB);
			if (this.isPartMember(v)) {
				LinkedList<Integer> part = this.processPathPart(v, this.llB);
				this.listB.addAll(part);
				this.vertexesToAdd = this.vertexesToAdd - part.size();
			} else {
				this.listB.add(v);
				this.vertexesToAdd--;
			}
		} else {
			startB = r.nextInt(this.rest.size());
			v = this.rest.remove(startB);
			if (this.isPartMember(v)) {
				LinkedList<Integer> part = this.processPathPart(v, this.rest);
				this.listB.addAll(part);
				this.vertexesToAdd = this.vertexesToAdd - part.size();
			} else {
				this.listB.add(v);
				this.vertexesToAdd--;
			}
		}

		// System.out.println("=============");
		// System.out.println("A:");
		this.printList(listA);
		// System.out.println();
		// System.out.println("B:");
		this.printList(listB);
		// System.out.println("=============");
		// System.out.println();
		while (this.vertexesToAdd > 0) {
			this.addOneAvailable(EOrigin.EITHER);
			// System.out.println("=============");
			// System.out.println("A:");
			this.printList(listA);
			// System.out.println();
			// System.out.println("B:");
			this.printList(listB);
			// System.out.println("=============");
			// System.out.println();
		}
	}

	private void generateOneList(EOrigin a) {
		int startA;
		int startB;
		int v;
		Random r = new Random();

		if (a == EOrigin.B) {
			if (this.llA.size() > 0) {
				startA = r.nextInt(this.llA.size());
				v = this.llA.remove(startA);
				if (this.isPartMember(v)) {
					LinkedList<Integer> part = this
							.processPathPart(v, this.llA);
					this.listA.addAll(part);
					this.vertexesToAdd = this.vertexesToAdd - part.size();
				} else {
					this.listA.add(v);
					this.vertexesToAdd--;
				}
			} else {
				startA = r.nextInt(this.rest.size());
				v = this.rest.remove(startA);
				if (this.isPartMember(v)) {
					LinkedList<Integer> part = this.processPathPart(v,
							this.rest);
					this.listA.addAll(part);
					this.vertexesToAdd = this.vertexesToAdd - part.size();
				} else {
					this.listA.add(v);
					this.vertexesToAdd--;
				}
			}

			// System.out.println("=============");
			// System.out.println("A:");
			this.printList(listA);
			// System.out.println();
			// System.out.println("B:");
			this.printList(listB);
			// System.out.println("=============");
			// System.out.println();
			while (this.vertexesToAdd > 0) {
				this.addOneAvailable(EOrigin.B);
				// System.out.println("=============");
				// System.out.println("A:");
				this.printList(listA);
				// System.out.println();
				// System.out.println("B:");
				this.printList(listB);
				// System.out.println("=============");
				// System.out.println();
			}
		} else if (a == EOrigin.A) {
			if (this.llB.size() > 0) {
				startB = r.nextInt(this.llB.size());
				v = this.llB.remove(startB);
				if (this.isPartMember(v)) {
					LinkedList<Integer> part = this
							.processPathPart(v, this.llB);
					this.listB.addAll(part);
					this.vertexesToAdd = this.vertexesToAdd - part.size();
				} else {
					this.listB.add(v);
					this.vertexesToAdd--;
				}
			} else {
				startB = r.nextInt(this.rest.size());
				v = this.rest.remove(startB);
				if (this.isPartMember(v)) {
					LinkedList<Integer> part = this.processPathPart(v,
							this.rest);
					this.listB.addAll(part);
					this.vertexesToAdd = this.vertexesToAdd - part.size();
				} else {
					this.listB.add(v);
					this.vertexesToAdd--;
				}
			}

			// System.out.println("=============");
			// System.out.println("A:");
			// this.printList(listA);
			// System.out.println();
			// System.out.println("B:");
			// this.printList(listB);
			// System.out.println("=============");
			// System.out.println();
			while (this.vertexesToAdd > 0) {
				this.addOneAvailable(EOrigin.A);
				// System.out.println("=============");
				// System.out.println("A:");
				this.printList(listA);
				// System.out.println();
				// System.out.println("B:");
				this.printList(listB);
				// System.out.println("=============");
				// System.out.println();
			}
		} else
			throw new RuntimeException("Error while generating one list!");
	}

	private void addOneAvailable(EOrigin ignore) {
		int chosen = -1;
		int bestDist = Integer.MAX_VALUE;
		EAttachmentPosition attachmentPosition = EAttachmentPosition.UNDEFINED;
		EOrigin origin = EOrigin.UNASSGIGNED;

		int firstA = -1;
		int lastA = -1;
		int firstB = -1;
		int lastB = -1;

		if (origin != EOrigin.A) {
			firstA = this.listA.getFirst();
			lastA = this.listA.getLast();
		}
		if (origin != EOrigin.B) {
			firstB = this.listB.getFirst();
			lastB = this.listB.getLast();
		}

		// System.out.println("firstA=" + firstA + ", lastA=" + lastA
		// + ", firstB=" + firstB + ", lastB=" + lastB);
		// System.out.println(this.llA.size() + ", " + this.llB.size() + ", "
		// + this.rest.size());

		if (ignore != EOrigin.A) {
			for (Integer i : this.llA) {
				int distFirstA = this.vertexes.getDistanceBetween(i, firstA);
				int distLastA = this.vertexes.getDistanceBetween(i, lastA);

				if (distFirstA < bestDist) {
					chosen = i;
					bestDist = distFirstA;
					attachmentPosition = EAttachmentPosition.A_BEGIN;
					origin = EOrigin.A;
				}

				if (distLastA < bestDist) {
					chosen = i;
					bestDist = distLastA;
					attachmentPosition = EAttachmentPosition.A_END;
					origin = EOrigin.A;
				}
			}
		}

		if (ignore != EOrigin.B) {
			for (Integer i : this.llB) {
				int distFirstB = this.vertexes.getDistanceBetween(i, firstB);
				int distLastB = this.vertexes.getDistanceBetween(i, lastB);

				if (distFirstB < bestDist) {
					chosen = i;
					bestDist = distFirstB;
					attachmentPosition = EAttachmentPosition.B_BEGIN;
					origin = EOrigin.B;
				}

				if (distLastB < bestDist) {
					chosen = i;
					bestDist = distLastB;
					attachmentPosition = EAttachmentPosition.B_END;
					origin = EOrigin.B;
				}
			}
		}

		for (Integer i : this.rest) {
			if (ignore != EOrigin.A) {
				int distFirstA = this.vertexes.getDistanceBetween(i, firstA);
				int distLastA = this.vertexes.getDistanceBetween(i, lastA);

				if (distFirstA < bestDist) {
					chosen = i;
					bestDist = distFirstA;
					attachmentPosition = EAttachmentPosition.A_BEGIN;
					origin = EOrigin.EITHER;
				}

				if (distLastA < bestDist) {
					chosen = i;
					bestDist = distLastA;
					attachmentPosition = EAttachmentPosition.A_END;
					origin = EOrigin.EITHER;
				}
			}

			if (ignore != EOrigin.B) {
				int distFirstB = this.vertexes.getDistanceBetween(i, firstB);
				int distLastB = this.vertexes.getDistanceBetween(i, lastB);

				if (distFirstB < bestDist) {
					chosen = i;
					bestDist = distFirstB;
					attachmentPosition = EAttachmentPosition.B_BEGIN;
					origin = EOrigin.EITHER;
				}

				if (distLastB < bestDist) {
					chosen = i;
					bestDist = distLastB;
					attachmentPosition = EAttachmentPosition.B_END;
					origin = EOrigin.EITHER;
				}
			}
		}

		// System.out.println(chosen + ", " + attachmentPosition + ", " +
		// origin);

		this.glueNew(chosen, attachmentPosition, origin);
	}

	private void glueNew(int chosen, EAttachmentPosition attachmentPosition,
			EOrigin origin) {
		LinkedList<Integer> originList;
		switch (origin) {
		case A:
			originList = this.llA;
			break;
		case B:
			originList = this.llB;
			break;
		case EITHER:
			originList = this.rest;
			break;
		default:
			throw new RuntimeException("Crossing failed");
		}
		if (this.isPartMember(chosen)) {
			originList.remove(originList.indexOf(Integer.valueOf(chosen)));
			LinkedList<Integer> part = this.processPathPart(chosen, originList);
			switch (attachmentPosition) {
			case A_BEGIN:
				Collections.reverse(part);
				this.listA.addAll(0, part);
				// System.out.print(this.vertexesToAdd + " - " + part.size()
				// + " = ");
				this.vertexesToAdd -= part.size();
				// System.out.println(this.vertexesToAdd);
				break;
			case A_END:
				this.listA.addAll(part);
				// System.out.print(this.vertexesToAdd + " - " + part.size()
				// + " = ");
				this.vertexesToAdd -= part.size();
				// System.out.println(this.vertexesToAdd);
				break;
			case B_BEGIN:
				Collections.reverse(part);
				this.listB.addAll(0, part);
				// System.out.print(this.vertexesToAdd + " - " + part.size()
				// + " = ");
				this.vertexesToAdd -= part.size();
				// System.out.println(this.vertexesToAdd);
				break;
			case B_END:
				this.listB.addAll(part);
				// System.out.print(this.vertexesToAdd + " - " + part.size()
				// + " = ");
				this.vertexesToAdd -= part.size();
				// System.out.println(this.vertexesToAdd);
				break;
			default:
				throw new RuntimeException("Crossing failed");
			}
		} else {
			originList.remove(originList.indexOf(Integer.valueOf(chosen)));
			switch (attachmentPosition) {
			case A_BEGIN:
				this.listA.addFirst(chosen);
				this.vertexesToAdd--;
				break;
			case A_END:
				this.listA.addLast(chosen);
				this.vertexesToAdd--;
				break;
			case B_BEGIN:
				this.listB.addFirst(chosen);
				this.vertexesToAdd--;
				break;
			case B_END:
				this.listB.addLast(chosen);
				this.vertexesToAdd--;
				break;
			default:
				throw new RuntimeException("Crossing failed");
			}
		}
	}

	private boolean isPartMember(int v) {
		if (this.findNeighbourForVertex(v) == -1) {
			return false;
		}
		return true;
	}

	private LinkedList<Integer> processPathPart(int first,
			LinkedList<Integer> available) {
		LinkedList<Integer> res = new LinkedList<Integer>();

		int actual = first;
		System.out.println(actual);
		int next = this.findNeighbourForVertex(actual);
		while (next >= 0) {
			res.add(actual);
			for (int i = 0; i < 2; i++) {
				if (this.vertexNeighbours[actual][i] == next) {
					this.vertexNeighbours[actual][i] = -1;
				}
				if (this.vertexNeighbours[next][i] == actual) {
					this.vertexNeighbours[next][i] = -1;
				}
			}
			actual = next;
			next = this.findNeighbourForVertex(actual);
		}

		res.add(actual);
		// System.out.println(actual);
		available.remove(available.indexOf(Integer.valueOf(actual)));

		return res;
	}

	private int findNeighbourForVertex(int v) {
		int res = this.vertexNeighbours[v][0];
		if (res >= 0) {
			return res;
		}
		res = this.vertexNeighbours[v][1];
		if (res >= 0) {
			return res;
		}
		return -1;
	}

	private void init() {
		this.vertexCountVector = new int[this.vertexes.getNumberOfNodes()];
		this.vertexNeighbours = new int[this.vertexes.getNumberOfNodes()][2];
		for (int i = 0; i < this.vertexes.getNumberOfNodes(); i++) {
			for (int j = 0; j < 2; j++) {
				this.vertexNeighbours[i][j] = -1;
			}
		}
		this.sameInA = 0;
		this.sameInB = 0;
		this.commonEdges = new HashSet<Edge>();
		this.availableVertexes = new LinkedList<Integer>();
		this.generateListOfAvailAbles();
		this.findCommonVertexesSets(this.firstResult, this.secondResult);
		this.sieveWithAvailables();
	}

	private void generateListOfAvailAbles() {
		Set<Edge> edgesA = this.transformResultToEdgeSet(this.firstResult);
		this.compareResults(edgesA, this.secondResult);
	}

	private void sieveWithAvailables() {
		this.sieveSet(this.llA);
		this.sieveSet(this.llB);
		this.sieveSet(this.rest);
	}

	private void sieveSet(LinkedList<Integer> set) {
		for (Iterator<Integer> i = set.iterator(); i.hasNext();) {
			Integer v = i.next();
			if (this.vertexNeighbours[v][0] >= 0
					&& this.vertexNeighbours[v][1] >= 0) {
				i.remove();
			}
		}
	}

	private Set<Edge> transformResultToEdgeSet(IResultHolder result) {
		Set<Edge> out = new HashSet<Edge>();
		int prev;

		if (result.getListA().size() > 1) {
			prev = result.getListA().getLast();
			for (int i : result.getListA()) {
				out.add(new Edge(i, prev));
				prev = i;
			}
		}

		if (result.getListB().size() > 1) {
			prev = result.getListB().getLast();
			for (int i : result.getListB()) {
				out.add(new Edge(i, prev));
				prev = i;
			}
		}

		return out;
	}

	private void compareResults(Set<Edge> res1, IResultHolder res2) {
		int prev;

		if (res2.getListA().size() == 2) {
			Edge e = new Edge(res2.getListA().getFirst(), res2.getListA()
					.getLast());
			int first = res2.getListA().getFirst();
			int last = res2.getListA().getLast();
			if (res1.contains(e)) {
				this.commonEdges.add(e);
				this.vertexCountVector[first]++;
				this.vertexCountVector[last]++;
				if (this.vertexNeighbours[first][0] < 0) {
					this.vertexNeighbours[first][0] = last;
				} else {
					this.vertexNeighbours[first][1] = last;
				}
				if (this.vertexNeighbours[last][0] < 0) {
					this.vertexNeighbours[last][0] = first;
				} else {
					this.vertexNeighbours[last][1] = first;
				}
				this.sameInA++;
			}
		} else if (res2.getListA().size() > 2) {
			prev = res2.getListA().getLast();
			for (int i : res2.getListA()) {
				Edge e = new Edge(prev, i);
				if (res1.contains(e)) {
					this.commonEdges.add(e);
					this.vertexCountVector[prev]++;
					this.vertexCountVector[i]++;
					if (this.vertexNeighbours[prev][0] < 0) {
						this.vertexNeighbours[prev][0] = i;
					} else {
						this.vertexNeighbours[prev][1] = i;
					}
					if (this.vertexNeighbours[i][0] < 0) {
						this.vertexNeighbours[i][0] = prev;
					} else {
						this.vertexNeighbours[i][1] = prev;
					}
					this.sameInA++;
				}
				prev = i;
			}
		}

		if (res2.getListB().size() == 2) {
			Edge e = new Edge(res2.getListB().getFirst(), res2.getListB()
					.getLast());
			int first = res2.getListB().getFirst();
			int last = res2.getListB().getLast();
			if (res1.contains(e)) {
				this.commonEdges.add(e);
				this.vertexCountVector[first]++;
				this.vertexCountVector[last]++;
				if (this.vertexNeighbours[first][0] < 0) {
					this.vertexNeighbours[first][0] = last;
				} else {
					this.vertexNeighbours[first][1] = last;
				}
				if (this.vertexNeighbours[last][0] < 0) {
					this.vertexNeighbours[last][0] = first;
				} else {
					this.vertexNeighbours[last][1] = first;
				}
				this.sameInB++;
			}
		} else if (res2.getListB().size() > 2) {
			prev = res2.getListB().getLast();
			for (int i : res2.getListB()) {
				Edge e = new Edge(prev, i);
				if (res1.contains(e)) {
					this.commonEdges.add(e);
					this.vertexCountVector[prev]++;
					this.vertexCountVector[i]++;
					if (this.vertexNeighbours[prev][0] < 0) {
						this.vertexNeighbours[prev][0] = i;
					} else {
						this.vertexNeighbours[prev][1] = i;
					}
					if (this.vertexNeighbours[i][0] < 0) {
						this.vertexNeighbours[i][0] = prev;
					} else {
						this.vertexNeighbours[i][1] = prev;
					}
					this.sameInB++;
				}
				prev = i;
			}
		}

		for (int i = 0; i < this.vertexes.getNumberOfNodes(); i++) {
			if ((this.vertexNeighbours[i][0] >= 0 && this.vertexNeighbours[i][1] < 0)
					|| (this.vertexNeighbours[i][0] < 0 && this.vertexNeighbours[i][1] >= 0)
					|| (this.vertexNeighbours[i][0] < 0 && this.vertexNeighbours[i][1] < 0)) {
				this.availableVertexes.add(i);
			}
		}
	}

	private void findCommonVertexesSets(IResultHolder firstResult,
			IResultHolder secondResult) {
		this.llA = new LinkedList<Integer>();
		this.llB = new LinkedList<Integer>();
		this.rest = new LinkedList<Integer>();
		Set<Integer> setA1 = new HashSet<Integer>(firstResult.getListA());
		Set<Integer> setA2 = new HashSet<Integer>(secondResult.getListA());
		Set<Integer> setB1 = new HashSet<Integer>(firstResult.getListB());
		Set<Integer> setB2 = new HashSet<Integer>(secondResult.getListB());
		int similarityAA = this.findSimilarity(setA1, setA2)
				+ this.findSimilarity(setB1, setB2);
		int similarityAB = this.findSimilarity(setA1, setB2)
				+ this.findSimilarity(setB1, setA2);
		if (similarityAA > similarityAB) {
			this.fillCommonVertexes(llA, setA1, setA2);
			this.fillCommonVertexes(llB, setB1, setB2);
		} else {
			this.fillCommonVertexes(llA, setA1, setB2);
			this.fillCommonVertexes(llB, setB1, setA2);
		}
		this.addRest(rest, llA, llB);
	}

	private void fillCommonVertexes(LinkedList<Integer> common,
			Set<Integer> set1, Set<Integer> set2) {
		for (Integer i : this.availableVertexes) {
			if (set1.contains(i) && set2.contains(i)) {
				common.add(i);
			}
		}
	}

	private int findSimilarity(Set<Integer> set1, Set<Integer> set2) {
		int count = 0;
		for (Integer i : set1) {
			if (set2.contains(i)) {
				count = count + 1;
			}
		}
		return count;
	}

	private void addRest(LinkedList<Integer> rest, LinkedList<Integer> set1,
			LinkedList<Integer> set2) {
		for (Integer i : this.availableVertexes) {
			if (!set1.contains(i) && !set2.contains(i)) {
				rest.add(i);
			}
		}
	}

	private void printList(List<Integer> list) {
		for (int i : list) {
			System.out.print(i + " ");
		}
		// System.out.println();
		// System.out.println("n = " + list.size());
	}

	private void printVertexNeighbours() {
		// System.out.println("Vertex Neighbours:");
		for (int i = 0; i < this.vertexes.getNumberOfNodes(); i++) {
			// System.out.print(i + ") ");
			for (int j = 0; j < 2; j++) {
				System.out.print(this.vertexNeighbours[i][j] + " ");
			}
			// System.out.println();
		}
	}

	@Override
	public int getLengthA() {
		return this.calculateLength(this.listA);
	}

	@Override
	public int getLengthB() {
		return this.calculateLength(this.listB);
	}

	@Override
	public LinkedList<Integer> getListA() {
		return this.listA;
	}

	@Override
	public LinkedList<Integer> getListB() {
		return this.listB;
	}

	@Override
	public Vertexes getVertexes() {
		return this.vertexes;
	}

	@Override
	public int compareTo(IResultHolder o) {
		int local = this.getLengthA() + this.getLengthB();
		int other = o.getLengthA() + o.getLengthB();
		return local - other;
	}
}
